package suffiztreegenerators;

import tree.*;

public class McCreights {
	
	public Tree generateSuffixTree(String x){
		
		if(x.isEmpty()){
			System.out.println("x is empty");
			return null;
		}
		
		Node head, root, nextHead;
		root = new Node(0, -1);
		Tree tree = new Tree(x, root);
		
		root.addChildren(new Node (0, x.length()-1));
				
		nextHead = root;
		for(int i = 0; i < x.length()-1; i++){
//			System.out.println(x.substring(i));
			head = nextHead;
			nextHead = null;
			
			if(head == root){
				//head(i+1) = slowscan(root,s(tail(i)))
				ScanResult res = tree.slowScan(root, tail(i, x, head).substring(1));
				
				//add i+1 and head(i+1) as node if necessary
				nextHead = res.isEdge() ? splitTree(res.getLower(),res.getIndex()) : res.getLower();

				//Insert the new node
				Node newNode = new Node(i + res.getPatternIndex() + 1, x.length()-1);

				nextHead.addChildren(newNode);
				head.setSuffixLink(root);
				continue;
			}
			
			//u = parent(head(i))
			Node u = head.getParent();
			//v = label(u,head(i))
			String v = head.subString(x);
			ScanResult w;
			if(u != root){
				//w = fastscan(s(u),v)
				w = tree.fastScan(u.getSuffixLink(), v);
			} else {
				//w = fastscan("",v[2..|v|]) 
				w = tree.fastScan(root,v.substring(1));
			}
			Node wNode;
			if( w.isEdge() ){
				//if w is an edge then
				//add a node for w 
				//head(i+1) = w
				nextHead = splitTree(w.getLower(), w.getIndex());
				wNode = nextHead;
			} else {
				//else if w is a node then 
				//head(i+1) = slowscan(w,tail(i))
				//add head(i+1) as node if necessary

				ScanResult res = tree.slowScan(w.getLower() , tail(i, x, head));
				nextHead = res.isEdge() ? splitTree(res.getLower(),res.getIndex()) : res.getLower();
				wNode = w.getLower();
			}
			
			//s(head(i)) = w 
			head.setSuffixLink(wNode);
			//add leaf i+1 and edge between head(i+1) and i+1
			nextHead.addChildren(new Node(i + nextHead.getDepth()+1, x.length()-1));
		}
		return tree;
	}

	private String tail(int index, String s, Node head){
		return s.substring(head.getDepth() + index);
	}
	
	
	private Node splitTree(Node n, int i){
		Node parent, res;
		
		parent = n.getParent();
		
		res = new Node(n.getStartIndex(), n.getStartIndex() + i -1);
		
		parent.removeChildren(n);
		parent.addChildren(res);
		n.setStartIndex(n.getStartIndex()+i);
		res.addChildren(n);
		return res;
	}

}
